\(n\) 很小，可以树形 dp 或者区间 dp
。
设 f[i][j] 为从 \(i\)
到 \(j\) 的最大加分值，则有
f[i][j]=max(f[i][k-1]*f[k+1][j]+f[k][k])。
有一个小技巧，将 f[i][i-1] 全部设置为
1，这样的话搜索到叶子就也可以按照通式 dp 了。
对于输出前序遍历（根，左树，右树）我们再树形 dp 一下就行了。
树形 dp 比较清晰明了（但是耗内存）。不想写树形 dp
的话递推式如上。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
inline int read()
{
int x=0,w=1;char c=getchar();
while(!isdigit(c)){
if(c=='-')w=-1;
c=getchar();
}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
const int maxn=35;
int n;
int f[maxn][maxn],a[maxn],ro[maxn][maxn];
int search(int l,int r)
{
if(l>r)return 1;
if(l==r){ro[l][r]=l;return f[l][r];}
if(f[l][r])return f[l][r];
for(int w,i=l;i<=r;i++)
{
w=search(l,i-1)*search(i+1,r)+f[i][i];
if(w>f[l][r])f[l][r]=w,ro[l][r]=i;
}
return f[l][r];
}
void print(int l,int r)
{
if(l>r)return ;
printf("%d ",ro[l][r]);
print(l,ro[l][r]-1);
print(ro[l][r]+1,r);
}
int main()
{
n=read();
for(int i=1;i<=n;i++)f[i][i]=read();
search(1,n);
printf("%d\n",f[1][n]);
print(1,n);
return 0;
}
|
